package problem133_Clone_Graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class MySolution {
	 public class UndirectedGraphNode {
		      public int label;
		      public List<UndirectedGraphNode> neighbors;
		      public UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
	 }
	
	public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
		if(node==null)	return null;
		Queue<UndirectedGraphNode> queue=new LinkedList<>();
		queue.add(node);
		Map<UndirectedGraphNode,UndirectedGraphNode> oldToNew=new HashMap<>();
		while(!queue.isEmpty()){
			UndirectedGraphNode top=queue.poll();
			UndirectedGraphNode copyNode=null;
			if(oldToNew.containsKey(top)){
				copyNode=oldToNew.get(top);
			}else{
				copyNode=new UndirectedGraphNode(top.label);
				oldToNew.put(top, copyNode);
			}
			for(UndirectedGraphNode nei:top.neighbors){
				if(oldToNew.containsKey(nei)){
					copyNode.neighbors.add(oldToNew.get(nei));
				}else{
					UndirectedGraphNode n=new UndirectedGraphNode(nei.label);
					copyNode.neighbors.add(n);
					queue.add(nei);
					oldToNew.put(nei, n);
				}
			}
		}
		return oldToNew.get(node);
    }
}
